Алгоритм Кіруса — Бека

Алгоритм Кіруса — Бека (англ. Cyrus — Beck) — алгоритм відсікання відрізків довільним опуклим багатокутником. Був запропонований як ефективніша заміна алгоритму Коена — Сазерленда, який виконує відсікання за кілька ітерацій.

Опис алгоритму

Відрізки, що відсікаються представляються в параметричному вигляді:

$p(t)=p_{0}+t(p_{1}-p_{0}),t\in [0,1]$

де

p₀, p₁ — координати початку і кінця відрізка відповідно,

t — параметр.

Кожен відрізок, що відсікається, містить координати початку і кінця, а також два параметра t_A та t_B, що відповідають початку і кінцю відрізка. Для кожного відрізка, що відсікається P виконуються наступні дії:

• Ребра багатокутника, що відсікає, обходяться проти годинникової стрілки. Для кожного ребра E обчислюється параметр t_E, що описує перетин E з прямою, на якій лежить відрізок P. Обчислюється скалярний добуток вектора E та зовнішньої нормалі N, в залежності від знака якого виникає одна з наступних ситуацій:
  • E · N < 0 — відрізок P спрямований з внутрішньої на зовнішню сторону ребра E. У цьому випадку параметр t_A замінюється на t_E, якщо t_E > t_A.
  • E · N > 0 — відрізок P спрямований із зовнішньої на внутрішню сторону ребра E. У цьому випадку параметр t_B замінюється на t_E, якщо t_E < t_B.
  • E · N = 0 — відрізок P паралельний ребру E. Відрізок P відкидається як невидимий, якщо знаходиться праворуч від E.
• Якщо t_A $\leq$ t_B, то задана параметрами t_A та t_B частина відрізка P видима. В іншому випадку відрізок P повністю невидимий.

Див. також

• Алгоритм Ліанга–Барського
• Алгоритм Ніколла-Лі-Ніколла

Література

• Mike Cyrus, Jay Beck. «Generalized two- and three-dimensional clipping». Computers & Graphics, 1978: 23-28.
• James D. Foley. Computer graphics: principles and practice [Архівовано 31 травня 2016 у Wayback Machine.]. Addison-Wesley Professional, 1996. p. 117.

Посилання

• https://web.archive.org/web/20101203041134/http://cs1.bradley.edu/public/jcm/cs535CyrusBeck.html
• https://web.archive.org/web/20110725233122/http://softsurfer.com/Archive/algorithm_0111/algorithm_0111.htm